/* 
  冒泡排序
  思想：两两进行比较，每次把最大的元素冒泡到最右边
  时间复杂度O(n^2)
*/
class Bubble {
  constructor(compare) {
    this.compare = compare || ((a, b) => (a - b));
  }
  swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  sort(arr) {
    for(let i = 0; i < arr.length - 1; i++) {
      for(let j = 0; j < arr.length - 1 - i; j++) {
        if (this.compare(arr[j], arr[j + 1]) > 0) {
          this.swap(arr, j, j + 1)
        }
      }
    }
  }

  // 优化1：当进行一次或者多次排序后，可能数组已经就是有序了
  // 判断条件，如果没有交换操作，就一定hi是排好序了
  sort2(arr) {
    for(let i = 0; i < arr.length - 1; i++) {
      let isSwap = false;
      for(let j = 0; j < arr.length - 1 - i; j++) {
        if (this.compare(arr[j], arr[j + 1]) > 0) {
          this.swap(arr, j, j + 1)
          isSwap = true;
        }
      }
      if (!isSwap) {
        break
      }
    }
  }
  // 优化2：当进行交货次数是，有可能是后面的几个元素同时排好序了，就不用在进行排序了
  // 比如第二次时： 312456，发现同时有几个元素已经排序完毕，所以可以减少递归的次数
  sort3(arr) {
    for(let i = 0; i < arr.length - 1;) {
      let lastSwap = 0;
      for(let j = 0; j < arr.length - 1 - i; j++) {
        if (this.compare(arr[j], arr[j + 1]) > 0) {
          this.swap(arr, j, j + 1)
          lastSwap = j + 1;
        }
      }
      // i时控制循环次数的 n时，i -> n - 2, lastSwap = m,那i = arr.length - lastSwap
      i = arr.length - lastSwap;
    }
  }
}

var arr = [34,23,13,24,35,77,6,3,21,]
var b = new Bubble();
// console.log(b.sort(arr), arr);
// console.log(b.sort2(arr), arr);
console.log(b.sort3(arr), arr);


